Field of the Invention
The present invention relates to an arithmetic technique for a coordinate transformation matrix for transforming two-dimensional or three-dimensional coordinate data into two two-dimensional coordinate data.
Description of the Related Art
Projective transformation includes homography transformation which is transformation from a two-dimensional space to a two-dimensional space, and transformation from a three-dimensional space to a three-dimensional space. Calculating a homography transformation matrix or three-dimensional projective transformation matrix from coordinate data of corresponding points in two spaces is basic processing in computer vision. These matrices can be used in various applications such as the generation of a panoramic image, the correction of a projection position of a projector, camera calibration using a planar pattern, the deduction and restoration of a three-dimensional shape of an object, and the detection of an obstacle on a road surface.
The principle of a vibration-proofing function of a moving image camera, which is implemented by using the homography matrix, and a method of obtaining the homography matrix will be explained below, and the problems will be described after that.
Blurring between consecutive frames obtained by capturing a moving image is detected as a geometric transform matrix, and the image is reversely corrected by a matrix obtained by smoothing the geometric transform matrix over ten-odd frames. This makes it possible to smooth blurring between the frames, and implement a vibration-proofing function when capturing a moving image.
When the distance from a camera to an object is sufficiently long and no problem arises even if the individual points of interest of the object are regarded as existing on the same plane, a geometric transform matrix expressing blurring between frames can be represented by a homography matrix, and the coordinates of pixels in these frames can be associated with each other by:
                                          λ            ⁡                          [                                                                                          x                      1                                                                                                                                  y                      1                                                                                                            1                                                              ]                                =                                    [                                                                    a                                                        b                                                        c                                                                                        d                                                        e                                                        f                                                                                        g                                                        h                                                        1                                                              ]                        ⁡                          [                                                                                          u                      1                                                                                                                                  v                      1                                                                                                            1                                                              ]                                      ⁢                                  ⁢                  λ          =                                    gu              1                        +                          hv              1                        +            1                                              (        1        )            
In equation (1), a 3×3 matrix on the right-hand side is a homography matrix, and a pixel having coordinates (u, v) in the preceding frame is converted into coordinates (x, y). Also, equation (1) can express non-linear projective transformation by a linear arithmetic operation by using homogeneous coordinates.
When the ninth element in the lower right corner of the 3×3 matrix of equation (1) is set at 1 as standardization, eight other elements can take free values, and a matrix having a degree of freedom of 8 is obtained. On the other hand, when coordinates in two images represented by the relationship of equation (1) are developed, two equations indicated by equation (2) below are obtained:(gu1+hv1+1)x1=au1+bv1+c (gu1+hv1+1)y1=du1+ev1+f  (2)
Eight equations, that is, simultaneous equations with eight unknowns can be obtained from four pairs of corresponding points, and one homography matrix can be obtained by solving these simultaneous equations. It is, however, assumed that three arbitrary points of these four coordinate points do not exist on a straight line.
By using the method as described above, homography matrices are obtained for a combination of four feature points in images and evaluated, and a matrix having the best evaluation result is selected and used as a homography matrix representing the relationship between the images. A deduction method like this is known as RANSAC deduction. To obtain a highly evaluated matrix, it is necessary to obtain and evaluate homography matrices for as many feature point combinations as possible, and the number is a few hundred to a few thousand per image.
A Gauss iteration method and Gauss-Jordan iteration method are well known as methods of solving the abovementioned simultaneous equations. However, the operation amount is large, and an operation error on numerical calculations sometimes increases. A method called pivot is, of course, usable as a measure to eliminate these inconveniences, but the processing amount further increases if this method is executed.
A literature “Paul S. Heckbert, “Fundamentals of Texture Mapping and Image Warping”, Master Thesis, Department of Electrical Engineering and Computer Science, University of California, Berkeley, June, 1989” describes a method of deducing a homography matrix between images by an approach entirely different from the aforementioned method. The method disclosed in this literature will briefly be explained below.
When deducing a homography matrix from image 1 to image 2, a unit square is defined in a space different from these images. Then, a first homography matrix H1 from this unit square to image 1 and a second homography matrix H2 from the unit square to image 2 are deduced. After that, an inverse matrix H1−1 of the first homography matrix H1 is multiplied by the second homography matrix H2, and H2·H1−1 is calculated as a homography matrix from image 1 to image 2.
This method requires the processes of deducing two homography matrices, calculating an inverse matrix of one homography matrix, and multiplying the inverse matrix of the one homography matrix by the other homography matrix.
In an application like a vibration-proofing function of an imaging apparatus such as a video camera, hundreds to thousands of feature points are extracted from one frame, and corresponding points are searched for between frames. Then, as many homography matrices as possible are deduced and calculated for various combinations of the corresponding points within one frame time. Consequently, a homography matrix having a higher evaluation can be obtained. Therefore, each matrix deduction must be performed at high speed. Also, matrix deduction can be performed for more feature point combinations by aborting the matrix deducing process if four feature points have linearity. To do that, however, a linearity determining process must be added to the existing matrix deducing process.